\documentclass{llncs}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[pdftex]{graphicx}
\usepackage{longtable}
\usepackage{soul}
\usepackage{hyperref}
\usepackage[portuguese]{babel}
\usepackage{float}
\usepackage{listings}
\usepackage{makeidx}  % allows for indexgeneration

\usepackage{tabulary}
\usepackage{wrapfig}
\usepackage{amssymb}

\lstset{ %
language=Prolog,
basicstyle=\footnotesize\ttfamily,       % the size of the fonts that are used for the code
% numbers=left,                   % where to put the line-numbers
% numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
% stepnumber=5,                   % the step between two line-numbers. If it's 1 each line 
%                                 % will be numbered
% numbersep=5pt,                  % how far the line-numbers are from the code
% %backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
showtabs=false,                 % show tabs within strings adding particular underscores
% frame=single,                   % adds a frame around the code
% tabsize=2,                  % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
% title=\lstname,                 % show the filename of files included with \lstinputlisting;
%                                 % also try caption instead of title
%escapeinside={\%*}{*)},         % if you want to add a comment within your code
%morekeywords={*,...}            % if you want to add more keywords to the set
}


\title{Utilização de Programação com Restrições para a Alocação de
  Médicos num Centro de Saúde}

% Isto e um comentario (So para nao ter que andar a ver os emails
% José Estevinho ei08122
% Omar Castro - ei08158
% Rolando Pereira - ei08150

\author{José Estevinho, Omar Castro e Rolando Pereira}

\institute{FEUP-PL, Turma 3MIEIC5, Grupo 502}

\begin{document}

\maketitle

\begin{abstract}

  Todos os centros de saúde requerem a presença de um médico em
  serviço quando estão abertos. Neste artigo demonstrámos um método,
  utilizando programação com restrições, para poder escolher médicos
  para um centro de saúde de maneira a minimizar o custo total dos
  salários. Para implementar os algoritmos será usado o módulo de
  programação com restrições da implementação Prolog da
  SICStus\cite{sicstus:homepage}. Mostraremos que a utilização deste paradigma de programação
  permitiu-nos criar um algoritmo simples e eficiente para a
  atribuição de horários de modo a que exista a todas as horas um
  médico presente no centro de saúde.

\end{abstract}

\section{Introdução}

Este artigo tem como objectivo a criação de um algoritmo de alocação
de médicos de forma a que, dado um horário e um conjunto de médicos,
exista sempre um médico activo a todas as horas com o menor custo
possível em termos de salários.

O algoritmo para efectuar estas as colocações considera os salários de
cada médico bem como o número máximo de horas que este pode trabalhar.

Existem dois limites a impôr no número de horas. Em primeiro lugar um
médico pode ter um limite de horas diário, específico a cada dia da
semana.  Por outro lado, o número semanal de horas que o médico
trabalha também não pode exceder um determinado limite.

Este artigo encontra-se dividido em várias secções, começando primeiro
por descrever de forma mais extensa o problema que será abordado.

Iremos depois mostrar os dados que foram usados para testar o
algoritmo, seguido de uma descrição das variáveis de decisão e
restrições usadas na implementação do mesmo.

Falaremos também das opções passadas ao predicado $labeling$ do
SICStus que ajudaram a tornar o algoritmo mais eficiente.

Por fim iremos apresentar um predicado que permite a visualização
simples dos resultados obtidos pelo algoritmo e serão também descritos
os resultados obtidos.

\section{Descrição do Problema}

No problema analisado neste artigo existe num centro de saúde que
requer a presença de um médico sempre que se encontra aberto ao
público. O horário de funcionamento do centro de saúde é das 8 às 16
horas de Segunda-feira a Sexta-feira e das 8 às 12 horas ao Sábado, ou
seja, o centro de saúde encontra-se aberto 44 horas por semana.

Para que tal critério possa acontecer existe uma lista de médicos com
os quais se pode fazer contractos à hora. No entanto, esses médicos só
podem trabalhar no centro de saúde um certo número de horas por
semana. Para além disso, certos médicos podem só poder trabalhar um
número limitado de horas em certos dias, ou até mesmo não poderem
trabalhar em certos dias da semana.

Para terminar, os médicos também podem preferir trabalhar a certos
dias da semana, sendo que esses dias deverão de ser atribuidos com
base no número de anos que esse médico trabalha para o centro de
saúde. O algoritmo não considera, no estado actual, esta situação.

O objectivo do problema é a criação de um horário em que exista sempre
um médico presente no centro de saúde e de forma a que o custo em
termos de salários seja o menor possível.

\section{Ficheiros de Dados}

O algoritmo deve poder receber como argumentos uma lista de médicos,
os respectivos salários e os seus limites, diários e semanais, de
horas que podem trabalhar na clínica.

Ao receber estes argumentos, o algoritmo deve de construir uma lista
que indique, para cada hora em que a clínica se encontra aberta, qual
o médico que deverá ficar de serviço. O algoritmo deverá também
devolver o custo total dos salários dos médicos, tendo em atenção, que
um dos objectivos do algoritmo é encontrar a solução que leva ao menor
custo.

Os dados que foram usados para testar o algoritmo estão indicados nas
tabelas \ref{tab:dataset_simples}, \ref{tab:dataset_enunciado},
\ref{tab:dataset_edge}, \ref{tab:dataset_mais_5_medicos} e \ref{tab:dataset_menos_5_medicos}.

Os dados da tabela \ref{tab:dataset_edge} ajudam a testar o algoritmo
no caso de o número de horas semanais que os médicos podem trabalhar
ser igual ao número de horas que a clínica se encontra aberta, ou
seja, o caso da soma dos valores da coluna ``Limite Horas Semanais''
ser igual a 44.

Os dados das tabelas \ref{tab:dataset_mais_5_medicos} e
\ref{tab:dataset_menos_5_medicos} ajudam a testar o algoritmo com
diferentes números de médicos.

Para verificar como o algoritmo reage quando recebe um elevado número
de médicos, estão também definidos no código dos anexos mais dois
conjuntos de dados que contêm 16 e 30 médicos, definidos,
respectivamente, nas tabelas \ref{tab:dataset_16_medicos} e
\ref{tab:dataset_30_medicos}. No entanto, esses dados não serão
listados nesta secção para não ultrapassar o limite de páginas deste
artigo.

\begin{table}[h!]
  \begin{center}
    \begin{tabular}{|c|c|c|c|}
      \hline
      Médico  &  Salário Hora  &  Limite Horas Semanais  &  Restrições adicionais  \\
      \hline
      A       &            60  &                      8  &                          \\
      B       &            65  &                      7  &                          \\
      C       &            50  &                      5  &                          \\
      D       &            70  &                     14  &                          \\
      E       &            50  &                      2  &                          \\
      \hline
    \end{tabular}
    \caption{Dados usados para testar sem ter restrições adicionais}
    \label{tab:dataset_simples}
  \end{center}
\end{table}

\begin{table}[h!]
  \begin{center}
    \begin{tabular}{|c|c|c|c|}
      \hline
      Médico  &  Salário Hora  &  Limite Horas Semanais  &  Restrições adicionais                   \\
      \hline
      A       &            60  &                     12  &  Não está disponível à Segunda-feira      \\
      B       &            65  &                      9  &  Só pode trabalhar 2 horas à Terça-feira  \\
      C       &            50  &                      8  &                                           \\
      D       &            70  &                     12  &                                           \\
      E       &            50  &                      6  &  Não está disponível ao Sábado            \\
      \hline
    \end{tabular}
    \caption{Dados usados para testar com valores gerais}
    \label{tab:dataset_enunciado}
  \end{center}
\end{table}

\begin{table}[h!]
  \begin{center}
    \begin{tabular}{|c|c|c|c|}
      \hline
      Médico  &  Salário Hora  &  Limite Horas Semanais  &  Restrições adicionais  \\
      \hline
      A       &            60  &                      7  &                          \\
      B       &            65  &                      6  &                          \\
      C       &            50  &                      9  &                          \\
      D       &            70  &                     12  &                          \\
      E       &            50  &                     10  &                          \\
      \hline
    \end{tabular}
    \caption{Dados usados para testar o caso fronteira}
    \label{tab:dataset_edge}
  \end{center}
\end{table}

\begin{table}[h!]
  \begin{center}
    \begin{tabular}{|c|c|c|c|}
      \hline
      Médico  &  Salário Hora  &  Limite Horas Semanais  &  Restrições adicionais  \\
      \hline
      1  &            60  &                     12  &                         \\
      2  &            65  &                      9  &                         \\
      3  &            50  &                      8  &                         \\
      4  &            70  &                     12  &                         \\
      5  &            50  &                      6  &                         \\
      6  &            70  &                      5  &                         \\
      7  &            65  &                      2  &
      \\
      \hline
    \end{tabular}
    \caption{Dados usados para testar o algoritmo com mais do que 5
      médicos}
    \label{tab:dataset_mais_5_medicos}
  \end{center}
\end{table}

\begin{table}[h!]
  \begin{center}
    \begin{tabular}{|c|c|c|c|}
      \hline
      Médico  &  Salário Hora  &  Limite Horas Semanais  &  Restrições adicionais  \\
      \hline
      1  &            60  &                     12  &                         \\
      2  &            65  &                     12  &                         \\
      3  &            50  &                     13  &                         \\
      4  &            70  &                     16  &                         \\
      \hline
    \end{tabular}
    \caption{Dados usados para testar o algoritmo com menos do que 5
      médicos}
    \label{tab:dataset_menos_5_medicos}
  \end{center}
\end{table}

\section{Variáveis de Decisão}

O algoritmo utiliza um conjunto de variáveis de decisão para encontrar
a solução óptima.

A variável que se quer preencher com o uso ao $labeling$ tem o nome
$Horas$ e corresponde a uma lista de 44 inteiros, correspondendo às 44
horas que o centro de saúde se encontra aberto ao público. O domínio
dos valores de $Horas$ será entre o número 1 e o número total de
médicos passados como argumento ao algoritmo. Cada inteiro contido na
variável $Horas$ indica o número do médico que deverá estar de serviço
nessa hora.

A outra variável de decisão é a variável $Salario$ que corresponde à
soma dos salários que o centro de saúde terá que pagar aos médicos. O
algoritmo encontra o menor valor possível para essa variável passando
ao $labeling$ a opção $minimize(Salario)$. O domínio dessa variável é
um valor correspondendo à soma das horas que cada médico vai passar
semanalmente no centro de saúde a multiplicar pelo seu salário.

\section{Restrições}

O algoritmo faz uso de um conjunto alargado de restrições.

A primeira restrição que o algoritmo cria serve para indicarmos que a
variável $Horas$ é um lista de 44 inteiros correspondentes ao número
de horas que o centro de saúde está aberto por semana.

Após adquirirmos o número total de médicos disponíveis torna-se também
possível restringir o domínio da variável $Horas$, que só poderá ter
valores entre 1 e o número total de médicos disponíveis, que é
representado no SICStus pela variável $TotalMedicos$.

Como cada médico pode ter em certos dias um limite máximo de horas
para trabalhar, é necessário criar restrições que impeçam um médico de
trabalhar num dado dia, mais horas do que aquelas que ele pode
trabalhar.

Essas restrições são criadas pelo predicado $limite\_horas$ que recebe
três argumentos:

\begin{itemize}
\item $Medicos$ $\rightarrow$ Lista de inteiros correspondente aos
  médicos que foram passados como argumento ao algoritmo principal;
\item $Horas$ $\rightarrow$ Lista de 44 variáveis de domínio que
  correspondem às 44 horas semanais que o centro de saúde se encontra aberto;
\item $LimitesDiarios$ $\rightarrow$ Lista de listas com 6 inteiros,
  em que cada um corresponde ao número total de horas que o médico
  pode trabalhar nesse dia. Caso não haja limite, o valor que aparece
  nesse dia é 8 (se for num dia de Segunda a Sexta) ou 4 (se for ao
  sábado) que corresponde ao número de horas que o centro de saúde
  está aberto nesse dia.
\end{itemize}

Esse predicado cria depois restrições que limitam o número de horas
que o médico pode trabalhar em cada dia.

Por exemplo, se o médico número 1 só poder trabalhar 2 horas à
Segunda-Feira, seriam criadas as seguintes restrições:

\begin{lstlisting}
count(1, Segunda, #=, HorasMedicoSEG), HorasMedicoSEG in 0..2
\end{lstlisting}

Onde $Segunda$ corresponde aos primeiros 8 valores da variável
$Horas$.

Após criar estas restrições é necessário guardar numa lista o número
de horas que cada médico vai trabalhar durante a semana.

Essa lista, com o nome $HorasMedicos$ é criada com um número de
variáveis de domínio igual ao valor $TotalMedicos$, sendo depois esta
lista passada ao predicado $count\_horas$ que recebe três argumentos:

\begin{itemize}
\item $Medicos$ $\rightarrow$ Lista de inteiros correspondente aos
  médicos que foram passados como argumento ao algoritmo principal;
\item $Horas$ $\rightarrow$ Lista de 44 variáveis de domínio que
  correspondem às 44 horas semanais que o centro de saúde se encontra aberto;
\item $HorasSemanaisMedicos$ $\rightarrow$ Lista de variáveis de
  domínio que irão conter o número de horas semanais que cada médico
  vai trabalhar.
\end{itemize}

Este predicado cria restrições que se limitam a contar os diferentes
inteiros que aparecem na variável $Horas$.

Por exemplo, se fosse necessário contar as horas do médico 1, iria ser
criada a seguinte restrição:

\begin{lstlisting}
count(1, Horas, #=, HorasMedico)
\end{lstlisting}

Onde $HorasMedico$ corresponde à cabeça da lista
$HorasSemanaisMedicos$.

Para acelerar o processo de $labeling$ são criadas novas restrições
que indicam o número de horas que cada médico terá que trabalhar ao
longo da semana.

Essas restrições são criadas pelo predicado $calcula\_limite\_horas$
que recebe três argumentos:

\begin{itemize}
\item $Salarios$ $\rightarrow$ Lista de inteiros que corresponde aos
  salários de cada médico. Esta lista é passada como argumento ao
  algoritmo principal;
\item $HorasSemanaisMedicos$ $\rightarrow$ Lista de variáveis de
  domínio que irão conter o número de horas semanais que cada médico
  vai trabalhar;
\item $LimitesSemanais$ $\rightarrow$ Lista de inteiros que
  corresponde ao número de horas máximo que cada médico pode trabalhar
  durante a semana. Esta lista é passada como argumento ao algoritmo principal.
\end{itemize}

O predicado $calcula\_limite\_horas$ procura o médico com o maior
salário, usando as restrições maximum e element. Uma vez encontrado, o
predicado vai tirando as horas do médico mais caro até que a soma
chegue ao número total de horas da semana que é 44.

Caso tirando todo o tempo do médico e a soma dos tempos disponíveis
ainda for maior que o número total de dias, o predicado procura o
segundo médico mais caro, criando uma lista em que o salário máximo é
nulo permitindo assim identificar o próximo salário mais elevado.

Quando a soma das disponibilidades chegar à soma das horas, faz-se as
restrições das horas de cada médico.

Por outro lado, quando a soma das disponibilidades for menor que o
total de horas, o predicado termina.

\section{Estratégia de Pesquisa}

O objectivo do algoritmo é usar o $labeling$ para preencher a variável
$Horas$ com inteiros correspondentes aos números dos médicos que terão
que estar presentes no centro de saúde a uma dada hora da semana.

No entanto, é necessário que o $labeling$ preencha a variável $Horas$
de tal forma que o centro de saúde tenha que pagar o menor custo
possível em termos de salários. Isso é conseguido passando ao $labeling$ a opção
$minimize(Salario)$.

Para melhorar a performance do $labeling$ é-lhe indicado que comece o
processamento pelas variáveis de domínio com menor domínio e maior
número de restrições. Para tal é passado ao $labeling$ a opção $ffc$.

Desta forma, a instrução de $labeling$ usada no algoritmo é a
seguinte:

\begin{lstlisting}
  labeling([ffc, minimize(Salario)], Horas)
\end{lstlisting}

\section{Visualização da Solução}

Para permitir uma maior facilidade em observar os resultados do
algoritmo, é chamado, depois do $labeling$ terminar, um predicado
$visualizador$ que permite ver em modo de texto, o número dos médicos
que deverão de estar no centro de saúde a cada hora da semana.

O predicado $visualizador$ recebe dois argumentos:

\begin{itemize}
\item $Horas$ $\rightarrow$ Lista de inteiros que indica o número do
  médico que deverá estar no centro de saúde a cada hora;
\item $Salario$ $\rightarrow$ Inteiro que indica o custo total que o
  centro de saúde terá que pagar semanalmente aos médicos.
\end{itemize}

Segue-se o output do predicado $visualizador$ quando utilizados os
dados das tabelas \ref{tab:dataset_simples},
\ref{tab:dataset_enunciado}, \ref{tab:dataset_edge},
\ref{tab:dataset_mais_5_medicos} e \ref{tab:dataset_menos_5_medicos}.


\begin{lstlisting}[caption=Output do $visualizador$ quando usados os
  dados da tabela \ref{tab:dataset_simples}]
       Seg. Ter. Qua. Qui. Sex. Sab.
  8-9   1    1    2    3    4    5
 9-10   1    1    2    3    4    5
10-11   1    1    2    3    4    5
11-12   1    1    2    3    4    5
12-13   1    2    2    3    4    
13-14   1    2    3    4    4    
14-15   1    2    3    4    5    
15-16   1    2    3    4    5    
 Total de salario a pagar: 2635
\end{lstlisting}

\begin{lstlisting}[caption=Output do $visualizador$ quando usados os
  dados da tabela \ref{tab:dataset_enunciado}]
       Seg. Ter. Qua. Qui. Sex. Sab.
  8-9   2    1    2    3    4    1
 9-10   2    1    3    4    4    1
10-11   2    1    3    4    5    1
11-12   2    1    3    4    5    1
12-13   2    1    3    4    5    
13-14   2    1    3    4    5    
14-15   2    1    3    4    5    
15-16   2    1    3    4    5    
 Total de salario a pagar: 2635
\end{lstlisting}

\begin{lstlisting}[caption=Output do $visualizador$ quando usados os
  dados da tabela \ref{tab:dataset_edge}]
       Seg. Ter. Qua. Qui. Sex. Sab.
  8-9   1    2    3    4    5    1
 9-10   1    3    3    4    5    1
10-11   1    3    4    4    5    1
11-12   2    3    4    4    5    1
12-13   2    3    4    4    5    
13-14   2    3    4    4    5    
14-15   2    3    4    5    5    
15-16   2    3    4    5    5    
 Total de salario a pagar: 2600
\end{lstlisting}

\begin{lstlisting}[caption=Output do $visualizador$ quando usados os
  dados da tabela \ref{tab:dataset_mais_5_medicos}]
       Seg. Ter. Qua. Qui. Sex. Sab.
  8-9   1    1    2    3    5    6
 9-10   1    1    2    3    5    6
10-11   1    1    2    3    5    7
11-12   1    1    2    3    5    7
12-13   1    2    2    3    5    
13-14   1    2    3    4    6    
14-15   1    2    3    4    6    
15-16   1    2    3    5    6    
 Total de salario a pagar: 2625
\end{lstlisting}

\begin{lstlisting}[caption=Output do $visualizador$ quando usados os
  dados da tabela \ref{tab:dataset_menos_5_medicos}]
       Seg. Ter. Qua. Qui. Sex. Sab.
  8-9   1    1    2    3    3    4
 9-10   1    1    2    3    3    4
10-11   1    1    2    3    3    4
11-12   1    1    2    3    3    4
12-13   1    2    2    3    3    
13-14   1    2    2    3    4    
14-15   1    2    2    3    4    
15-16   1    2    2    3    4    
 Total de salario a pagar: 2640
\end{lstlisting}

\section{Resultados}

Para analisar o algoritmo recorremos ao predicado do SICStus
$fd\_statistics$\cite{sicstus:stat_predicate} que nos indica várias propriedades do algoritmo como
por exemplo o número de retrocessos efectuados pelo $labeling$.

% TODO: Referencia ao manual do sictus para a parte do fd_statistics
O predicado $fd\_statistics$ foi usado da seguinte forma (o uso do
predicado $dataset1$ serve apenas a título de exemplo):

\begin{lstlisting}
dataset1(Medicos, Salarios, LimitesDiarios, LimitesSemanais),
centro_saude(Medicos, Salarios, LimitesDiarios, 
             LimitesSemanais, Horas, Salario),
             fd_statistics.
\end{lstlisting}


Como se pode ver na tabela \ref{tab:estatisticas} o algoritmo é
bastante eficiente para diversos inputs, fazendo muito poucos
backtracks apesar de criar muitas restrições.
   
\begin{table}
  \begin{center}
    \begin{tabulary}{12.3cm}{|C|C|C|C|C|C|}
      \hline
      &  Dados tabela \ref{tab:dataset_simples}  & Dados tabela \ref{tab:dataset_enunciado} & Dados tabela \ref{tab:dataset_edge} &  Dados tabela \ref{tab:dataset_mais_5_medicos} & Dados tabela \ref{tab:dataset_menos_5_medicos} \\
      \hline
      Resumptions  &                                    2021  &                                    1918  &                               2082  &                                          3037  &                                          1530  \\
      Entailments  &                                     963  &                                     937  &                                941  &                                          1343  &                                           773  \\
      Prunings     &                                    1671  &                                    1633  &                               1643  &                                          2316  &                                          1346  \\
      Backtracks   &                                      38  &                                      38  &                                 34  &                                            42  &                                            37  \\
      Constraints  &                                     489  &                                     489  &                                475  &                                           679  &                                           394  \\
      \hline
    \end{tabulary}
    \caption{Output do predicado $fd\_statistics$ para os vários
      conjuntos de dados}
    \label{tab:estatisticas}
  \end{center}
\end{table}

\section{Conclusões e Perspectivas de Desenvolvimento}

Vimos neste projecto que é possível criar um sistema de atribuição de
horários de forma eficiente, usando a metodologia de Programação com
Restrições, quer em termos de tempo gasto a programar os algoritmos,
quer em termos de tempo de CPU gasto ao correr esses algoritmos.

No entanto, apesar das vantagens mencionadas, existe também algumas
limitações com o algoritmo, como por exemplo não ter em consideração
os dias em que cada médico preferia trabalhar ou o número de anos que
esse médico já trabalhou para o centro de saúde.

De tal forma, uma maneira de melhorar o algoritmo desenvolvido seria
modifi\-cando-o para ter em conta essas situações.

% Bibliografia
\begin{thebibliography}{1}

\bibitem{sicstus:homepage}
  http://www.sics.se/isl/sicstuswww/site/index.html
\bibitem{sicstus:stat_predicate}
  http://www.sics.se/sicstus/docs/latest4/html/sicstus.html/Statistics-Predicates.html

\end{thebibliography}

\newpage

%% Mudar para o modo anexos
\appendix
\section{Anexos}

\subsection{Novos conjuntos de dados}

\begin{table}[h!]
  \begin{center}
    \begin{tabulary}{\textwidth}{|C|C|C|C|}
      \hline
      \parbox[c]{5em}{Médico}  &  Salário Hora  &  Limite Horas Semanais  &  Restrições adicionais                                                    \\
      \hline
      1  &            60  &                     12  &  Não está disponível à Segunda-Feira                                      \\
      2  &            65  &                      9  &  Só pode trabalhar 2 horas à Terça-Feira                                  \\
      3  &            50  &                      8  &                                                                           \\
      4  &            70  &                     12  &                                                                           \\
      5  &            50  &                      6  &  Só pode trabalhar 3 horas à Sexta-Feira                                  \\
      6  &            60  &                     21  &  Só pode trabalhar 1 hora à Quinta-Feira                                  \\
      7  &            40  &                     10  &  Só pode trabalhar 3 horas à Quarta-Feira                                 \\
      8  &            65  &                      4  &  Só pode trabalhar 4 horas à Terça-Feira                                  \\
      9  &            70  &                     16  &  Só pode trabalhar 5 horas à Quinta-Feira                                 \\
      10  &            30  &                     10  &  Só pode trabalhar 3 horas à Quarta-Feira                                 \\
      11  &            50  &                      8  &  Só pode trabalhar 4 horas à Terça-Feira                                  \\
      12  &            61  &                      7  &  Só pode trabalhar 2 horas à Terça-Feira                                  \\
      13  &            54  &                      9  &  Só pode trabalhar 3 horas à Quarta-Feira e 2 horas ao Sábado             \\
      14  &            49  &                     12  &  Só pode trabalhar 4 horas à Terça-Feira e 6 horas à Quinta-Feira         \\
      15  &            60  &                     11  &                                                                           \\
      16  &            51  &                     13  &  Só pode trabalhar 7 horas à Quinta-Feira e não pode trabalhar ao Sábado  \\
      \hline
    \end{tabulary}
    \caption{Dados usados para testar o algoritmo com 16 médicos}
    \label{tab:dataset_16_medicos}
  \end{center}
\end{table}

\newpage

\begin{table}[h!]
  \begin{center}
    \begin{tabulary}{\textwidth}{|C|C|C|C|}
      \hline
      \parbox[c]{5em}{Medico}  &  Salário Hora  &  Limite Horas Semanais  &  Restrições adicionais                                                    \\
      \hline
      1  &            60  &                     12  &  Não está disponível à Segunda-Feira                                      \\
      2  &            65  &                      9  &  Só pode trabalhar 2 horas à Terça-Feira                                  \\
      3  &            50  &                      8  &                                                                           \\
      4  &            70  &                     12  &                                                                           \\
      5  &            50  &                      6  &  Só pode trabalhar 3 horas à Sexta-Feira                                  \\
      6  &            60  &                     21  &  Só pode trabalhar 1 hora à Quinta-Feira                                  \\
      7  &            40  &                     10  &  Só pode trabalhar 3 horas à Quarta-Feira                                 \\
      8  &            65  &                      4  &  Só pode trabalhar 4 horas à Terça-Feira                                  \\
      9  &            70  &                     16  &  Só pode trabalhar 5 horas à Quinta-Feira                                 \\
      10  &            30  &                     10  &  Só pode trabalhar 3 horas à Quarta-Feira                                 \\
      11  &            50  &                      8  &  Só pode trabalhar 4 horas à Segunda-Feira e Terça-Feira                  \\
      12  &            61  &                      7  &  Só pode trabalhar 7 horas à Terça-Feira e 5 horas à Quinta-Feira         \\
      13  &            54  &                      9  &  Só pode trabalhar 3 horas à Quarta-Feira e 6 horas à Quinta-Feira        \\
      14  &            49  &                     12  &  Só pode trabalhar 4 horas à Terça-Feira                                  \\
      15  &            60  &                     11  &  Só pode trabalhar 2 horas à Terça-Feira                                  \\
      16  &            51  &                     13  &  Só pode trabalhar 3 horas à Quarta-Feira                                 \\
      17  &            45  &                     10  &  Só pode trabalhar 4 horas à Terça-Feira                                  \\
      18  &            52  &                      9  &  Só pode trabalhar 5 horas à Quinta-Feira                                 \\
      19  &            56  &                      8  &  Só pode trabalhar 3 horas à Quarta-Feira e 2 horas ao Sábado             \\
      20  &            26  &                      6  &  Só pode trabalhar 3 horas à Terça-Feira e 6 horas à Quinta-Feira         \\
      21  &            32  &                      8  &  Só pode trabalhar 7 horas à Quinta-Feira e não pode trabalhar ao Sábado  \\
      22  &            26  &                     10  &  Só pode trabalhar 6 horas à Terça-Feira e 3 horas à Quarta-Feira         \\
      23  &            64  &                     30  &  Só pode trabalhar 3 horas à Terça-Feira e 5 horas à Quinta-Feira         \\
      24  &            58  &                      9  &  Só pode trabalhar 3 horas à Terça-Feira e 5 horas à Quinta-Feira         \\
      25  &            65  &                      6  &  Só pode trabalhar 3 horas à Quarta-Feira                                 \\
      26  &            75  &                      8  &  Só pode trabalhar 4 horas à Terça-Feira                                  \\
      27  &            25  &                      5  &  Só pode trabalhar 5 horas à Quinta-Feira                                 \\
      28  &            36  &                     32  &  Só pode trabalhar 3 horas à Quarta-Feira                                 \\
      29  &            89  &                     12  &  Só pode trabalhar 4 horas à Terça-Feira                                  \\
      30  &            90  &                      9  &  Só pode trabalhar 5 horas à Quinta-Feira                                 \\
      \hline
    \end{tabulary}
    \caption{Dados usados para testar o algoritmo com 30 médicos}
    \label{tab:dataset_30_medicos}
  \end{center}
\end{table}

\newpage

\subsection{Output do predicado $visualizador$ para novos conjuntos de
  dados}

\begin{lstlisting}[caption=Output do $visualizador$ quando usados os
  dados da tabela \ref{tab:dataset_16_medicos}]
       Seg. Ter. Qua. Qui. Sex. Sab.
  8-9   14    5    7    7    10    14
 9-10   14    5    7    7    10    14
10-11   14    5    7    7    11    14
11-12   14    5    10    10    11    14
12-13   14    7    10    10    11    
13-14   14    7    10    10    11    
14-15   14    7    11    10    11    
15-16   14    7    11    10    11    
 Total de salario a pagar: 1888
\end{lstlisting}

\begin{lstlisting}[caption=Output do $visualizador$ quando usados os
  dados da tabela \ref{tab:dataset_30_medicos}]
       Seg. Ter. Qua. Qui. Sex. Sab.
  8-9   27    10    20    21    22    10
 9-10   27    10    20    21    22    10
10-11   27    10    20    21    22    10
11-12   28    10    20    21    22    10
12-13   28    10    21    22    22    
13-14   28    10    21    22    22    
14-15   28    20    21    22    27    
15-16   28    20    21    22    27    
 Total de salario a pagar: 1277
\end{lstlisting}

\subsection{Output do predicado $fd\_statistics$ para os novos
  conjuntos de dados}

\begin{table}[h!]
  \begin{center}
    \begin{tabular}{|c|c|c|}
      \hline
                   &  Dados da tabela \ref{tab:dataset_16_medicos}  & Dados da tabela \ref{tab:dataset_30_medicos}  \\
      \hline
      Resumptions  &                                         14196  &       45498  \\
      Entailments  &                                          2282  &        4355  \\
      Prunings     &                                          4644  &        8796  \\
      Backtracks   &                                            43  &          63  \\
      Constraints  &                                          1846  &        3874  \\
      \hline
    \end{tabular}
    \caption{Output do predicado $fd\_statistics$ para os dados das
      tabelas \ref{tab:dataset_16_medicos} e \ref{tab:dataset_30_medicos}}
    \label{tab:estatisticas-anexos}
  \end{center}
\end{table}

\newpage

\subsection{Código Fonte}

\begin{lstlisting}
:-use_module(library(clpfd)).

% Conjunto de datasets que sao descritos no relatorio
% Chamar no prolog com (substituir dataset1 pelo dataset desejado):
% dataset1(Medicos, Salarios, LimitesDiarios, LimitesSemanais),
%   centro_saude(Medicos, Salarios, LimitesDiarios, LimitesSemanais, Horas, Salario).

% Dataset1 do relatorio (Corresponde aos valores simples, ou seja, sem
% restricoes adicionais)
dataset1([1,2,3,4,5], [60,65,50,70,50], [[8,8,8,8,8,4],
                                         [8,8,8,8,8,4],
                                         [8,8,8,8,8,4],
                                         [8,8,8,8,8,4],
                                         [8,8,8,8,8,4]], [12,9,8,12,6]).

% Dataset2 do relatorio (Corresponde aos valores dados no enunciado)
dataset2([1,2,3,4,5], [60,65,50,70,50], [[0,8,8,8,8,4],
                                         [8,2,8,8,8,4],
                                         [8,8,8,8,8,4],
                                         [8,8,8,8,8,4],
                                         [8,8,8,8,8,0]], [12,9,8,12,6]).

% Dataset3 do relatorio (Corresponde ao conjunto de medicos com
% limites semanais que sao iguais ao numero de horas que o centro de
% saude esta aberto)
dataset3([1,2,3,4,5], [60,65,50,70,50], [[8,8,8,8,8,4],
                                         [8,8,8,8,8,4],
                                         [8,8,8,8,8,4],
                                         [8,8,8,8,8,4],
                                         [8,8,8,8,8,0]], [7,6,9,12,10]).

% Dataset4 do relatorio (mais do que 5 medicos)
dataset4([1,2,3,4,5,6,7], [60,65,50,70,50,70,65], [[8,8,8,8,8,4],
                                                   [8,8,8,8,8,4],
                                                   [8,8,8,8,8,4],
                                                   [8,8,8,8,8,4],
                                                   [8,8,8,8,8,4],
                                                   [8,8,8,8,8,4],
                                                   [8,8,8,8,8,4]], [12,9,8,12,6,5,2]).

% Dataset5 do relatorio (menos do que 5 medicos)
dataset5([1,2,3,4], [60,65,50,70], [[8,8,8,8,8,4],
                                    [8,8,8,8,8,4],
                                    [8,8,8,8,8,4],
                                    [8,8,8,8,8,4]], [12,12,13,16]).

% Dataset6 do relatorio (16 medicos)
dataset6([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],
         [60,65,50,70,50,60,40,65,70,30,50,61,54,49,60,51],
         [[0,8,8,8,8,4],
          [8,2,8,8,8,4],
          [8,8,8,8,8,4],
          [8,8,8,8,8,4],
          [8,8,8,8,3,4],
          [8,8,8,1,8,4],
          [8,8,3,8,8,4],
          [8,4,8,8,8,4],
          [8,8,8,5,8,4],
          [8,8,3,8,8,4],
          [8,4,8,8,8,4],
          [8,2,8,8,8,4],
          [8,8,3,8,8,2],
          [8,4,8,6,8,4],
          [8,8,8,8,8,4],
          [8,8,8,7,8,0]],
         [12,9,8,12,6,21,10,4,16,10,8,7,9,12,11,13]).

% Dataset7 do relatorio (30 medicos)
dataset7([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
          16,17,18,19,20,21,22,23,24,25,26,27,28,29,30],
         [60,65,50,70,50,60,40,65,70,30,50,61,54,49,60,
          51,45,52,56,26,32,26,64,58,65,75,25,36,89,90],
         [[0,8,8,8,8,4],
          [8,2,8,8,8,4],
          [8,8,8,8,8,4],
          [8,8,8,8,8,4],
          [8,8,8,8,3,4],
          [8,8,8,1,8,4],
          [8,8,3,8,8,4],
          [8,4,8,8,8,4],
          [8,8,8,5,8,4],
          [8,8,3,8,8,4],
          [4,4,8,8,8,4],
          [8,7,8,5,8,4],
          [8,8,3,6,8,4],
          [8,4,8,8,8,4],
          [8,2,8,8,8,4],
          [8,8,3,8,8,4],
          [8,4,8,8,8,4],
          [8,8,8,5,8,4],
          [8,8,3,8,8,2],
          [8,3,8,6,8,4],
          [8,8,8,7,8,0],
          [8,6,3,8,8,4],
          [8,3,8,5,8,4],
          [8,3,8,5,8,4],
          [8,8,3,8,8,4],
          [8,4,8,8,8,4],
          [8,8,8,5,8,4],
          [8,8,3,8,8,4],
          [8,4,8,8,8,4],
          [8,8,8,5,8,4]],
         [12,9,8,12,6,21,10,4,16,10,8,7,9,12,11,
          13,10,9,8,6,8,10,30,9,6,8,5,32,12,9]).



centro_saude(Medicos, Salarios, LimitesDiarios, LimitesSemanais, Horas, Salario) :-
    % De Segunda a Sexta o centro de saude esta aberto 8 horas
    % Ao Sabado ele esta aberto 4 horas
    % Numero total de horas que se encontra aberto por semana = 5*8+4 = 44
    length(Horas, 44),

	length(Medicos, TotalMedicos),
	domain(Horas, 1, TotalMedicos),

    limite_horas(Medicos, Horas, LimitesDiarios),

    length(HorasMedicos, TotalMedicos),
    count_horas(Medicos, Horas, HorasMedicos),

    % com estas restricoes garntimos que o custo total e minimo
    calcula_limite_horas(Salarios,HorasMedicos,LimitesSemanais),
    !, % Para evitar que o calcular_limite_horas volte a ser chamado

    calcular_salario(HorasMedicos, Salarios, Salario),
    labeling([ffc, minimize(Salario)], Horas),

    visualizador(Horas, Salario).

limite_horas([], _, []).
limite_horas([Medico|Restantes_medicos], Horas, [LimiteDiarios|Restantes_limites]) :-

    Horas = [Seg1, Seg2, Seg3, Seg4, Seg5, Seg6, Seg7, Seg8,
             Ter1, Ter2, Ter3, Ter4, Ter5, Ter6, Ter7, Ter8,
             Qua1, Qua2, Qua3, Qua4, Qua5, Qua6, Qua7, Qua8,
             Qui1, Qui2, Qui3, Qui4, Qui5, Qui6, Qui7, Qui8,
             Sex1, Sex2, Sex3, Sex4, Sex5, Sex6, Sex7, Sex8,
             Sab1, Sab2, Sab3, Sab4],
    Segunda = [Seg1, Seg2, Seg3, Seg4, Seg5, Seg6, Seg7, Seg8],
    Terca   = [Ter1, Ter2, Ter3, Ter4, Ter5, Ter6, Ter7, Ter8],
    Quarta  = [Qua1, Qua2, Qua3, Qua4, Qua5, Qua6, Qua7, Qua8],
    Quinta  = [Qui1, Qui2, Qui3, Qui4, Qui5, Qui6, Qui7, Qui8],
    Sexta   = [Sex1, Sex2, Sex3, Sex4, Sex5, Sex6, Sex7, Sex8],
    Sabado = [Sab1, Sab2, Sab3, Sab4],

    LimiteDiarios = [LimiteSegunda, LimiteTerca, LimiteQuarta, LimiteQuinta, LimiteSexta, LimiteSabado],

    count(Medico, Segunda, #=, HorasMedicoSEG), HorasMedicoSEG in 0..LimiteSegunda,
    count(Medico, Terca,   #=, HorasMedicoTER), HorasMedicoTER in 0..LimiteTerca,
    count(Medico, Quarta,  #=, HorasMedicoQUA), HorasMedicoQUA in 0..LimiteQuarta,
    count(Medico, Quinta,  #=, HorasMedicoQUI), HorasMedicoQUI in 0..LimiteQuinta,
    count(Medico, Sexta,   #=, HorasMedicoSEX), HorasMedicoSEX in 0..LimiteSexta,
    count(Medico, Sabado,  #=, HorasMedicoSAB), HorasMedicoSAB in 0..LimiteSabado,

    limite_horas(Restantes_medicos, Horas, Restantes_limites).

count_horas([], _, []).
count_horas([Num_medico|Restantes_medicos], Horas, [HorasMedico|Restantes_horas_medicos]) :-
    count(Num_medico, Horas, #=, HorasMedico),
    count_horas(Restantes_medicos, Horas, Restantes_horas_medicos).

calcular_salario([], [], 0).
calcular_salario([HorasMedico|Restantes_horas], [SalarioMedico|Restantes_salarios], Salario) :-
    calcular_salario(Restantes_horas, Restantes_salarios, Salario1),
    Salario is HorasMedico * SalarioMedico + Salario1.

calcula_limite_horas(_,HorasMedicos,LimiteHorasPorSemana):-
	sum(LimiteHorasPorSemana,#=,44),!,
        calcula_limites(HorasMedicos,LimiteHorasPorSemana).

calcula_limite_horas(_,_,LimiteHorasPorSemana):-
	sum(LimiteHorasPorSemana,#<,44),fail.


calcula_limite_horas(Salario,HorasMedicos,LimiteHorasPorSemana):-
	maximum(Caro,Salario),
	element(X,Salario,Caro),
	sum(LimiteHorasPorSemana,#=,Totalhoras),
	RestoHoras #= Totalhoras - 44 #/\ RestoHoras #> 0,
	element(X,LimiteHorasPorSemana,Hora),
	Hora #> RestoHoras,!,
	Temporetirado #= Hora-RestoHoras,
	modifica(X,Salario,0,Salario1),
	modifica(X,LimiteHorasPorSemana,Temporetirado,LimiteHorasPorSemana1),
	calcula_limite_horas(Salario1,HorasMedicos,LimiteHorasPorSemana1).

calcula_limite_horas(Salario,HorasMedicos,LimiteHorasPorSemana):-
	maximum(Caro,Salario),
	element(X,Salario,Caro),
	sum(LimiteHorasPorSemana,#=,Totalhoras),
	RestoHoras #= Totalhoras - 44 #/\ RestoHoras #> 0,
	element(X,LimiteHorasPorSemana,Hora),
	Hora #=< RestoHoras,!,
	modifica(X,Salario,0,Salario1),
	modifica(X,LimiteHorasPorSemana,0,LimiteHorasPorSemana1),
	calcula_limite_horas(Salario1,HorasMedicos,LimiteHorasPorSemana1).


calcula_limites([],[]).
calcula_limites([HorasMedico|Restantes_horas],[LimiteHoras|Restantes_limites]):-
	HorasMedico #= LimiteHoras,
		calcula_limites(Restantes_horas,Restantes_limites).

modifica(_,[],_,[]).
modifica(1, [_|XS], Valor, [Valor|XS]).
modifica(N, [X|XS], Valor, [X|ZS]) :-
	N1 #= N - 1,
        modifica(N1, XS,Valor , ZS).

%% interface grafica
i :- inicio.

inicio :- repeat,
	write('Alocacao de Medicos num Centro de Saude\n'),
	write('Qual dataset deseja utilizar?\n'),
	write(' 1- Dataset1 (valores simples, sem restricoes adicionais)\n'),
	write(' 2- Dataset2 (valores dados no enunciado)\n'),
	write(' 3- Dataset3 (conjunto de medicos com limites semanais que\n sao iguais ao numero de horas que o centro de saude esta aberto)\n'),
	write(' 4- Dataset4 (mais do que 5 medicos)\n'),
    write(' 5- Dataset5 (menos do que 5 medicos)\n'),
    write(' 6- Dataset6 (menos do que 16 medicos)\n'),
    write(' 7- Dataset7 (menos do que 30 medicos)\n'),
	write(' 0- Sair\n'),
	write('\nopcao: '),
	read(C),
	menu(C).  	
	
%% "Switch" das opcoes do menu  %% menu(+Numero, +Tabuleiro)
menu(0) :- !.

menu(1) :- !,
    dataset1(Medicos, Salarios, LimitesDiarios, LimitesSemanais),
	centro_saude(Medicos, Salarios, LimitesDiarios, LimitesSemanais, Horas, Salario).
	
menu(2) :- !,
    dataset2(Medicos, Salarios, LimitesDiarios, LimitesSemanais),
	centro_saude(Medicos, Salarios, LimitesDiarios, LimitesSemanais, Horas, Salario).
	
menu(3) :- !,
    dataset3(Medicos, Salarios, LimitesDiarios, LimitesSemanais),
	centro_saude(Medicos, Salarios, LimitesDiarios, LimitesSemanais, Horas, Salario).

menu(4) :- !,
    dataset4(Medicos, Salarios, LimitesDiarios, LimitesSemanais),
	centro_saude(Medicos, Salarios, LimitesDiarios, LimitesSemanais, Horas, Salario).

menu(5) :- !,
    dataset5(Medicos, Salarios, LimitesDiarios, LimitesSemanais),
	centro_saude(Medicos, Salarios, LimitesDiarios, LimitesSemanais, Horas, Salario).

menu(6) :- !,
    dataset6(Medicos, Salarios, LimitesDiarios, LimitesSemanais),
	centro_saude(Medicos, Salarios, LimitesDiarios, LimitesSemanais, Horas, Salario).

menu(7) :- !,
    dataset7(Medicos, Salarios, LimitesDiarios, LimitesSemanais),
	centro_saude(Medicos, Salarios, LimitesDiarios, LimitesSemanais, Horas, Salario).

visualizador(Horas, Salario) :- 
	Space = '    ',
    Horas = [Seg1, Seg2, Seg3, Seg4, Seg5, Seg6, Seg7, Seg8,
             Ter1, Ter2, Ter3, Ter4, Ter5, Ter6, Ter7, Ter8,
             Qua1, Qua2, Qua3, Qua4, Qua5, Qua6, Qua7, Qua8,
             Qui1, Qui2, Qui3, Qui4, Qui5, Qui6, Qui7, Qui8,
             Sex1, Sex2, Sex3, Sex4, Sex5, Sex6, Sex7, Sex8,
             Sab1, Sab2, Sab3, Sab4],

	write('       Seg. Ter. Qua. Qui. Sex. Sab.\n'),
	write('  8-9   ') ,write(Seg1), write(Space), write(Ter1), write(Space), write(Qua1), write(Space),
				write(Qui1), write(Space), write(Sex1), write(Space), write(Sab1), nl,
	write(' 9-10   ') ,write(Seg2), write(Space), write(Ter2), write(Space), write(Qua2), write(Space),
			write(Qui2), write(Space), write(Sex2), write(Space), write(Sab2), nl,
	write('10-11   ') ,write(Seg3), write(Space), write(Ter3), write(Space), write(Qua3), write(Space),
			write(Qui3), write(Space), write(Sex3), write(Space), write(Sab3), nl,
	write('11-12   ') ,write(Seg4), write(Space), write(Ter4), write(Space), write(Qua4), write(Space),
			write(Qui4), write(Space), write(Sex4), write(Space), write(Sab4), nl,
	write('12-13   ') ,write(Seg5), write(Space), write(Ter5), write(Space), write(Qua5), write(Space),
			write(Qui5), write(Space), write(Sex5), write(Space), nl,
	write('13-14   ') ,write(Seg6), write(Space), write(Ter6), write(Space), write(Qua6), write(Space),
			write(Qui6), write(Space), write(Sex6), write(Space), nl,
	write('14-15   ') ,write(Seg7), write(Space), write(Ter7), write(Space), write(Qua7), write(Space),
			write(Qui7), write(Space), write(Sex7), write(Space), nl,
	write('15-16   ') ,write(Seg8), write(Space), write(Ter8), write(Space), write(Qua8), write(Space),
			write(Qui8), write(Space), write(Sex8), write(Space), nl,
    write(' Total de salario a pagar: '), write(Salario), nl.
\end{lstlisting}

%\lstinputlisting[language=Prolog]{../centro-saude.pl}
\end{document}
